package LeetCode刷题;

import java.util.LinkedList;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-11-09 15:38
 * @description: Functions of this class is
 * 官方题解：
 * 用一个queue和一个deque实现
 * queue就是正常的que，负责push和pop
 * deque用来存放最大值
 * 如果新的value大于deque尾端的值，那么deque一直进行pop_back操作，直到尾端的值大于等于value 或者为空
 * 再将value压入deque的尾部
 * 每次取max_value，返回deque首部的值
 * 当que进行pop操作时，如果que首部的值等于deque首部的值，那么deque同样需要进行pop_front操作
 * 总结完毕！
 *
 * class MaxQueue {
 *     Queue<Integer> q;
 *     Deque<Integer> d;
 *
 *     public MaxQueue() {
 *         q = new LinkedList<Integer>();
 *         d = new LinkedList<Integer>();
 *     }
 *
 *     public int max_value() {
 *         if (d.isEmpty()) {
 *             return -1;
 *         }
 *         return d.peekFirst();
 *     }
 *
 *     public void push_back(int value) {
 *         while (!d.isEmpty() && d.peekLast() < value) {
 *             d.pollLast();
 *         }
 *         d.offerLast(value);
 *         q.offer(value);
 *     }
 *
 *     public int pop_front() {
 *         if (q.isEmpty()) {
 *             return -1;
 *         }
 *         int ans = q.poll();
 *         if (ans == d.peekFirst()) {
 *             d.pollFirst();
 *         }
 *         return ans;
 *     }
 * }
 *
 * *******就是滑动窗口模板题目！！！***********
 *
 **/
public class NoNoNo队列的最大值类似滑动窗口 {
    public static void main(String[] args) {

    }
    private LinkedList<Integer> queue;
    private LinkedList<Integer> maxQueue;
//    public NoNoNo队列的最大值() {
//        queue=new LinkedList<Integer>();
//        maxQueue=new LinkedList<Integer>();
//    }

    public int max_value() {
        if(!maxQueue.isEmpty()){
            return maxQueue.peekFirst();
        }
        return -1;
    }

    public void push_back(int value) {
        while(!maxQueue.isEmpty()&&value>maxQueue.peekLast()){//如果要插入的元素比最大队列中的大的话，就把小的元素出队，
            maxQueue.pollLast();
        }
        //直到剩下的元素都比要插入的元素大，在把该元素入队，其实就是为了维持最大队列中的单调递增性
        maxQueue.addLast(value);
        queue.add(value);
    }

    public int pop_front() {
        if(!queue.isEmpty()){
            if(queue.peek().equals(maxQueue.peekFirst())){
                maxQueue.pollFirst();
            }
            return queue.poll();
        }
        return -1;
    }
}